package exams.retest;

public class Solution {

    public static void main(String[] args) {
//        int[] arr = {1, 0, 3, 0, 4, 0, 5, 0, 6, 7, 8, 0, 10};
        String input = """
             BCDEFGH
             BAAHELL
             OOOOOLO
             DDDDDDD
             """;
        String[] lines = input.split("\n");
        char[][] matrix = new char[lines.length][lines[0].length()];
        for(int i =0; i < lines.length; i++) {
            for (int j = 0; j < lines[i].length(); j++) {
                matrix[i][j] = lines[i].charAt(j);
            }
        }
        int[] res = findWord("OOOOD", matrix);

        System.out.println(res[0] + " " + res[1]);
    }

    /**
     * n * m 数组填有 A-Z 字母
     * 求能否找到子字符串，返回字符串首字母所在位置
     *
     * ABCDEFG
     * BAAHELL
     * OOOOOLO
     * DDDDDDD
     *
     * 找到HELLO，返回H所在位置，只能上下左右找下一个，不能回头
     * */
    public static int[] findWord(String word, char[][] matrix) {
        int[] res = {-1, -1};
        boolean[][] mark = new boolean[matrix.length][matrix[0].length];

        for(int i=0; i<matrix.length; i++) {
            for(int j=0; j<matrix[i].length;j++) {
                if(matrix[i][j] == word.charAt(0)) {
                    if(dfs(matrix, mark, word, i, j, 0)) {
                        res[0] = i;
                        res[1] = j;
                    }
                }
            }
        }

        return res;
    }

    public static boolean dfs(char[][] matrix, boolean[][] mark, String word, int i, int j, int index) {
        if(index == word.length()) {
            return true;
        } else {
            if(i < 0 || j < 0 || i >= matrix.length || j >= matrix[i].length || mark[i][j]) {
                return false;
            }
            mark[i][j] = true;
            if(word.charAt(index) == matrix[i][j]) {
                if(dfs(matrix, mark, word, i, j - 1, index + 1) ||
                    dfs(matrix, mark, word, i -1, j, index+1) ||
                    dfs(matrix, mark, word, i, j +1, index + 1) ||
                    dfs(matrix, mark, word, i+1, j, index + 1)) {
                    return true;
                }
            }

            mark[i][j] = false;
            return false;
        }
    }
}
